package Other;

import java.util.ArrayList;
import java.util.List;

public class leet_70 {
}

class Solution_70 {
    public int climbStairs(int n) {
        int result = DynamicRegressionClimb(n);
        return result;
    }

    /**
     * 动态回归爬楼梯
     * 要从 n 层台阶 只有2中方法 n-1 走一步
     * n-2 走二步
     * 所以 step(n) = step(n-1) + step(n-2)
     * @param n 楼梯层数
     * @return
     */
    public int DynamicRegressionClimb(int n){
        if(n==0){
            return 0;
        }else if(n==1){
            return 1;
        }


        int[] result = new int[n+1];
        // 定义前二层
        result[1] = 1;
        result[2] = 2;

        for(int i=3; i<=n; i++){
            result[i] = result[i-1] + result[i-2];
        }
        return result[n];
    }

}
